public class L151 {
    public static void main(String[] args) {
//        String str = "the  sky is blue";
        String str = "  hello world  ";
        String reverseWords = new Solution().reverseWords(str);
        System.out.println(reverseWords);

    }


    static class Solution {
        public String reverseWords(String s) {
            char[] chars = s.toCharArray();
            StringBuilder sb = new StringBuilder();
            int left = 0;
            int right = chars.length - 1;
            while (chars[left] == ' ') left++;
            while (chars[right] == ' ') right--;
            while (left <= right) {
                char c = chars[left];
                if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                    sb.append(c);
                }
                left++;
            }

            reverse(0, sb.length() - 1, sb);

            int rl = 0;
            for (int i = 0; i < sb.length(); i++) {
                if (sb.charAt(i) == ' ') {
                    reverse(rl, i - 1, sb);
                    rl = i + 1;
                }
            }
            if (rl < sb.length()) {
                reverse(rl, sb.length() - 1, sb);
            }

            return sb.toString();

//            int rl = 0;
//            int length = chars.length;
//            for (int i = 0; i < length; i++) {
//                if (chars[i] == ' ') {
//                    reverse(rl, i - 1, chars);

//                    处理重复空格问题，但是遇到首尾空格会数组越界
//                    rl = i + 1;
//                    int j = i + 1;
//                    int spaceCount = 1;
//                    while (chars[j] == ' ') {
//                        spaceCount++;
//                        j++;
//                    }
//                    if (spaceCount > 1) {
//                        int k = i;
//                        while (k + spaceCount < length) {
//                            chars[k + 1] = chars[k + spaceCount];
//                            k++;
//                        }
//                        length = length - spaceCount + 1;
//                    }
//                }
//            }
//            if (rl < length - 1) {
//                reverse(rl, length - 1, chars);
//            }

//            return new String(chars, 0, length);
        }

        private void reverse(int left, int right, StringBuilder chars) {
            while (left < right) {
                char temp = chars.charAt(left);
                chars.setCharAt(left, chars.charAt(right));
                chars.setCharAt(right, temp);
                left++;
                right--;
            }
        }
    }

}
